#include"BinaryTree.h"


BinaryTree::BinaryTree()
{
    root = nullptr; //初始化为空树，二叉树可以是空的
}


void BinaryTree::Insert(const ElementType& element)
{
    root = InsertNode(root,element);
}

void BinaryTree::Remove(const ElementType& element)
{
    root = RemoveByElement(root,element);
}

BinaryTree::Node* BinaryTree::InsertNode(Node* node , const ElementType& element)
{
    if(node == nullptr)
        return new Node(element);
    
    if(node->data == element)
        return node;
    
    if(node->data > element)
    {
        //插入左子树
        node->left = InsertNode(node->left,element);
        if(LRDevition(node) > 1)
        {
            //左左
            if(node->left->data > element)
            {
                node = RotateRight(node);
            }
            else
            //左右
            {
                node = RotateLeftRight(node);
            }
        }
    }
    else
    {
        //插入右子树
        node->right = InsertNode(node->right,element);
        
        if(LRDevition(node) < -1)
        {
            if(node->right->data < element)
            {
                //右右
                node = RotateLeft(node);
            }
            else
            {
                //右左
                node = RotateRightLeft(node);
            }
        }
    }

    return node;
}




void BinaryTree::show()
{
    std::cout<<"前\n";
    PrevTravel(root);
    std::cout<<std::endl;

    std::cout<<"中\n";
    MidTravel(root);
    std::cout<<std::endl;
    
    std::cout<<"后\n";
    PostTravel(root);
    std::cout<<std::endl;

    std::cout<<"层序\n";
    HeightTravel(root);
    std::cout<<std::endl;
}



void BinaryTree::PrevTravel(Node* node)
{
    if(node == nullptr)
        return;
    
    std::cout<<node->data<<" ";
    PrevTravel(node->left);
    PrevTravel(node->right);
}

void BinaryTree::MidTravel(Node *node)
{
    if(node == nullptr)
        return;
    MidTravel(node->left);
    std::cout<<node->data<<" ";
    MidTravel(node->right);
}

void BinaryTree::PostTravel(Node *node)
{
    if(node == nullptr)
        return;
    PostTravel(node->left);
    PostTravel(node->right);
    std::cout<<node->data<<" ";
}

void BinaryTree::HeightTravel(Node *node)
{
    LinkQueue q;
    q.Push(root);
    while (!q.IsEmpty())
    {
        Node* newnode = (Node*)*q.GetFront();
        std::cout<<newnode->data<<" ";
        if(newnode->left)
        {
            q.Push(newnode->left);
        }
        if(newnode->right)
        {
            q.Push(newnode->right);
        }
        q.Pop();
    }
    std::cout<<std::endl; 
}

BinaryTree::Node *BinaryTree::RemoveByElement(Node *node, const ElementType &element)
{
    if(node == nullptr)
        return nullptr;

    if(node->data < element)
    {
        node->right = RemoveByElement(node->right,element);
    }

    else if(node->data > element)
    {
        node->left = RemoveByElement(node->left,element);
    }   

    else
    {
        //当找到的是 叶结点，也就是没有子树
        if(node->left == nullptr && node->right == nullptr)
        {
            delete node;
            node = nullptr;
        }

        //当找到的 是 有两个孩子的 结点
        else if(node->left != nullptr && node->right != nullptr)
        {
            Node *min = GetMinNode(node->right);
            node->data = min->data;
            node->right = RemoveByElement(node->right,min->data);
        }

        //当找到的是只有一个孩子的
        else
        {
            Node* newnode = node->left ? node->left : node->right;//左孩子 和 右孩子，谁存在取谁
            delete node;
            node = newnode;
        }
    }

    if(LRDevition(node) > 1)
    {
        if(LRDevition(node->left) > 0)
        {
            //左左
            node = RotateRight(node);
        }
        else
        {
            //左右
            node = RotateLeftRight(node);
        }
    }
    else if(LRDevition(node) < -1)
    {
        if(LRDevition(node->right) > 0 )
        {
            //右左
            node = RotateRightLeft(node);
        }
        else
        {
            //右右
            node = RotateLeft(node);
        }
    }

    return node;
}


BinaryTree::ElementType* BinaryTree::FindByElement(const ElementType& element)
{
    return  FindNode(root,element);
}


BinaryTree::Node* BinaryTree::GetMinNode(Node* node)
{
    Node* min;
    while(node->left != nullptr)
    {
        min = node->left;
    }
    return min;
}



BinaryTree::Node* BinaryTree::RotateRight(Node*node)
{
    Node* p = node->left;
    node->left = p->right;
    p->right = node;
    return p; 
}

BinaryTree::Node* BinaryTree::RotateLeft(Node*node)
{
    Node* p = node->right;
    node->right = p->left;
    p->left = node;
    return p; 
}


BinaryTree::Node* BinaryTree::RotateRightLeft(Node*node)
{
    node->right = RotateRight(node->right);
    node = RotateLeft(node);
    return node;
}

BinaryTree::Node* BinaryTree::RotateLeftRight(Node*node)
{
    node->left = RotateLeft(node->left);
    node = RotateRight(node);
    return node;
}




BinaryTree::ElementType* BinaryTree::FindNode(Node*node , const ElementType&element)
{
    if(node == nullptr)
        return nullptr;
    
    if(node->data > element)
        return FindNode(node->left,element);
    
    else if(node->data < element)
        return FindNode(node->right,element);
    else
    {
        return &node->data;
    }
}











int BinaryTree::GetNodeHeight(Node*node)
{
    if(node == nullptr)
        return 0;
    
    int leftheight = GetNodeHeight(node->left);
    int rightheight = GetNodeHeight(node->right);

    return (leftheight > rightheight ? leftheight : rightheight) + 1;
}

int BinaryTree::LRDevition(Node*node)
{
    if(node == nullptr)
        return 0;
    return GetNodeHeight(node->left) - GetNodeHeight(node->right);
}











